"""
model name : aihw
file       : dfs.py
information:
    author : Yuu
    time   : 2025/10/10
"""
import copy
from utils.node import Node
from utils.utils import corr2index


class Dfs:
    def __init__(self, basemap, col=19, row=19):
        self.col = col
        self.row = row
        self.basemap = basemap
        self.start_node = Node(1, 1, 0)
        self.end_node = Node(self.col, self.row, 0)

    def set_start_node(self, x, y):
        self.start_node = Node(x, y, 0)

    def set_end_node(self, x, y):
        self.end_node = Node(x, y, 0)

    def get_neighbors(self, node):
        """获取邻居节点"""
        neighbors = []
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 上、右、下、左

        for dx, dy in directions:
            nx, ny = node.x + dx, node.y + dy
            if 0 < nx <= self.col and 0 < ny <= self.row:
                i, j = corr2index(nx, ny)
                if self.basemap[i][j] != -1:
                    neighbors.append(Node(nx, ny, self.basemap[i][j]))

        return neighbors

    @staticmethod
    def reconstruct_path(current_node: Node):
        """重构路径"""
        path = []
        all_weights = 0
        current = current_node

        while current is not None:
            all_weights += current.w
            path.append((current.x, current.y))
            current = current.parent

        path.reverse()
        return path, all_weights

    def solve(self):
        """基于权重的最优深度优先搜索"""
        # 初始化起点
        start_node = copy.deepcopy(self.start_node)
        start_node.g = 0  # 累计权重成本

        # 使用栈实现DFS，但按累计权重排序（模拟最佳优先）
        stack = [start_node]
        visited = {}  # 记录到达每个位置的最小权重
        visited[(start_node.x, start_node.y)] = start_node.g

        # 用于记录所有节点的字典
        all_nodes = {(start_node.x, start_node.y): start_node}

        # 用于记录搜索过程
        search_steps = []

        best_solution = None
        min_cost = float('inf')

        while stack:
            # 按累计权重排序，优先探索成本较低的路径
            stack.sort(key=lambda node: node.g, reverse=True)
            current_node = stack.pop()

            search_steps.append((current_node.x, current_node.y))

            # 检测是否到达终点
            if current_node.x == self.end_node.x and current_node.y == self.end_node.y:
                current_cost = current_node.g
                if current_cost < min_cost:
                    min_cost = current_cost
                    best_solution = current_node
                continue  # 继续搜索可能更优的路径

            # 如果当前路径成本已经超过已知最优解，剪枝
            if current_node.g >= min_cost:
                continue

            # 获取邻居节点
            for neighbor in self.get_neighbors(current_node):
                neighbor_corr = (neighbor.x, neighbor.y)

                # 计算新路径的成本
                new_cost = current_node.g + neighbor.w

                # 如果这个位置没访问过，或者找到了更低的成本路径
                if neighbor_corr not in visited or new_cost < visited[neighbor_corr]:
                    visited[neighbor_corr] = new_cost

                    # 创建新节点
                    if neighbor_corr not in all_nodes:
                        neighbor_node = copy.deepcopy(neighbor)
                        all_nodes[neighbor_corr] = neighbor_node
                    else:
                        neighbor_node = all_nodes[neighbor_corr]

                    # 更新节点信息
                    neighbor_node.parent = current_node
                    neighbor_node.g = new_cost

                    # 将邻居节点加入栈中
                    stack.append(neighbor_node)

        if best_solution:
            path, all_weight = self.reconstruct_path(best_solution)
            # 返回2个值以保持接口一致
            return path, search_steps, all_weight

        return None, search_steps, -1
